
{\magonebf  6.4 Sets of intervals (interval\_set)}

\decl interval\_set I

{\bf 1. Definition}

An instance $S$ of the parameterized data type \name\ is a 
collection of items ($is\_item$). Every item in $S$ contains a closed 
interval of the real numbers as key and an information from data type $I$, 
called the information type of $S$. The number of items in $S$ is called 
the size of $S$. An interval set of size zero is said to be empty. We use 
$<x,y,i>$ to denote the item with interval $[x,y]$ and information $i$, 
$x$ ($y$) is called the left (right) boundary of the item. For each 
interval $[x,y] \subset \real$ there is at most one item $<x,y,i> \in S$.



\bigskip
{\bf 2. Creation}

\create S {}

creates an instance \var\ of type \name\ and initializes \var\ to the 
empty set. 



\bigskip
{\bf 3. Operations}

\+\cleartabs & \hskip 2.6truecm & \hskip 5.5truecm &\cr
\+\op double     left {is\_item\ it}  
                            {returns the left boundary of item $it$.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op double     right {is\_item\ it} 
                                    {returns the right boundary of item $it$.}
\+\nop                              {\precond $it$ is an item in \var.}
\smallskip
\+\op I        inf {is\_item\ it}   
                                    {returns the information of item $it$.}
\+\nop                              {\precond $it$ is an item in \var.}
\smallskip
\+\op is\_item insert {double\ x,\ double\ y,\ I\ i} {}
\+\nop                {associates the information $i$ with interval}
\+\nop                {$[x,y]$. If there is an item $<x,y,j>$ in \var }
\+\nop                {then $j$ is replaced by $i$, else a new item }
\+\nop                {$<x,y,i>$ is added to $S$. In both cases }
\+\nop                {the item is returned.}
\smallskip
\+\op is\_item lookup {double\ x,\ double\ y} 
                      {returns the item with interval $[x,y]$}
\+\nop                {(nil if no such item exists in \var).}
\smallskip
\+\op list\<is\_item\>  intersection {double\ a,\ double\ b}  {}
\+\nop                {returns all items $<x,y,i>\ \in\ S$ with}
\+\nop                {$[x,y] \cap [a,b] \neq \emptyset$.}
\smallskip
\+\op void del {double\ x,\ double\ y}         
                      {deletes the item with interval $[x,y]$}
\+\nop                {from \var.}
\smallskip
\+\op void del\_item {is\_item\ it}   
                              {removes item $it$ from \var.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void change\_inf {is\_item\ it,\ I\ i} 
                              {makes $i$ the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void clear {}           
                              {makes \var\ the empty interval\_set.}
\smallskip 
\+\op bool empty {}           
                              {returns true iff \var\ is empty.}
\smallskip 
\+\op int  size {}            
                              {returns the size of \var.}



\bigskip
{\bf 4. Implementation}

Interval sets are implemented by two-dimensional range trees [Wi85, Lu78].
Operations insert, lookup, del\_item and del take time $O(\log^2 n)$,
intersection takes time $O(k + \log^2 n)$, where $k$ is the size
of the returned list. Operations left, right, inf, empty, and size
take time $O(1)$, and clear $O(n\log n)$. Here $n$ is always the 
current size of the interval set. The space requirement is $O(n\log n)$.

